/*
687. 最长同值路径
https://leetcode.cn/problems/longest-univalue-path/description/
中等 2024/12/4
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        // 调用辅助函数计算最长同值路径，并返回结果
        longestPath(root);
        return path;
    }

    int path = 0; // 初始化最长同值路径长度为0

    // 辅助函数，求以当前节点 "为起点"（表示向下发展）的最长同值路径长度
    int longestPath(TreeNode* node) {
        if (!node) return 0; // 空节点返回0

        // 计算左子树和右子树的最长同值路径长度
        int left = longestPath(node->left);    // 左子树的最长同值路径长度
        int right = longestPath(node->right);  // 右子树的最长同值路径长度

        // 计算从当前节点向左延伸的最长同值路径长度
        int leftPath = (node->left && node->left->val == node->val) ? left + 1 : 0;

        // 计算从当前节点向右延伸的最长同值路径长度
        int rightPath = (node->right && node->right->val == node->val) ? right + 1 : 0;

        // 更新全局最长同值路径长度
        path = max(path, leftPath + rightPath);

        // 返回以当前节点为起点的最长同值路径长度
        return max(leftPath, rightPath);
    }
};